Transform-based coding is a technique that is widely used in image and video compression, where compression is achieved via decomposing each component block or patch over a complete dictionary known to provide compaction. Recently, there has been a growing interest in using basis selection methods for signal approximation and compression. However, signal approximation using a linear combination of basis functions from an over-complete dictionary has proven to be an NP-hard problem.